#ifndef HTAB_H_
#define HTAB_H_
#define HTAB_EMPTY ((void *)0)
#define HTAB_DELETED ((void *)1)
#include <stdint.h>
#include <stddef.h>
#include <stdlib.h>
#include <string.h>
typedef unsigned int hashval_t;
struct prime_ent {
  hashval_t prime;
  hashval_t inv;
  hashval_t inv_m2; /* inverse of prime-2 */
  hashval_t shift;
};

static struct prime_ent const prime_tab[] = {
    {7, 0x24924925, 0x9999999b, 2},
    {13, 0x3b13b13c, 0x745d1747, 3},
    {31, 0x08421085, 0x1a7b9612, 4},
    {61, 0x0c9714fc, 0x15b1e5f8, 5},
    {127, 0x02040811, 0x0624dd30, 6},
    {251, 0x05197f7e, 0x073260a5, 7},
    {509, 0x01824366, 0x02864fc8, 8},
    {1021, 0x00c0906d, 0x014191f7, 9},
    {2039, 0x0121456f, 0x0161e69e, 10},
    {4093, 0x00300902, 0x00501908, 11},
    {8191, 0x00080041, 0x00180241, 12},
    {16381, 0x000c0091, 0x00140191, 13},
    {32749, 0x002605a5, 0x002a06e6, 14},
    {65521, 0x000f00e2, 0x00110122, 15},
    {131071, 0x00008001, 0x00018003, 16},
    {262139, 0x00014002, 0x0001c004, 17},
    {524287, 0x00002001, 0x00006001, 18},
    {1048573, 0x00003001, 0x00005001, 19},
    {2097143, 0x00004801, 0x00005801, 20},
    {4194301, 0x00000c01, 0x00001401, 21},
    {8388593, 0x00001e01, 0x00002201, 22},
    {16777213, 0x00000301, 0x00000501, 23},
    {33554393, 0x00001381, 0x00001481, 24},
    {67108859, 0x00000141, 0x000001c1, 25},
    {134217689, 0x000004e1, 0x00000521, 26},
    {268435399, 0x00000391, 0x000003b1, 27},
    {536870909, 0x00000019, 0x00000029, 28},
    {1073741789, 0x0000008d, 0x00000095, 29},
    {2147483647, 0x00000003, 0x00000007, 30},
    /* Avoid "decimal constant so large it is unsigned" for 4294967291.  */
    {0xfffffffb, 0x00000006, 0x00000008, 31}};

INLINE hashval_t
htab_hash_string(const char *s) {
  hashval_t ret = 0;
  const char *p;
  for (p = s; *p; p++) {
    ret = ret * 67 + ((unsigned)(*p) - 113);
  }
  return ret;
}

#define mix(a, b, c)                  \
  {                                   \
    a -= b;                           \
    a -= c;                           \
    a ^= (c >> 13);                   \
    b -= c;                           \
    b -= a;                           \
    b ^= (a << 8);                    \
    c -= a;                           \
    c -= b;                           \
    c ^= ((b & 0xffffffff) >> 13);    \
    a -= b;                           \
    a -= c;                           \
    a ^= ((c & 0xffffffff) >> 12);    \
    b -= c;                           \
    b -= a;                           \
    b = (b ^ (a << 16)) & 0xffffffff; \
    c -= a;                           \
    c -= b;                           \
    c = (c ^ (b >> 5)) & 0xffffffff;  \
    a -= b;                           \
    a -= c;                           \
    a = (a ^ (c >> 3)) & 0xffffffff;  \
    b -= c;                           \
    b -= a;                           \
    b = (b ^ (a << 10)) & 0xffffffff; \
    c -= a;                           \
    c -= b;                           \
    c = (c ^ (b >> 15)) & 0xffffffff; \
  }

typedef __intptr_t intptr_t;
static hashval_t
htab_hash_pointer(const void *p) {
  intptr_t v = (intptr_t)p;
  unsigned a, b, c;
  a = b = 0x9e3779b9;
  a += (hashval_t)(v >> (sizeof(intptr_t) * 8 / 2));
  b += (hashval_t)(v & (((intptr_t)1 << (sizeof(intptr_t) * 8 / 2)) - 1));
  c = 0x42135234;
  mix(a, b, c);
  return c;
}

INLINE int
htab_slot_is_empty(const void *slot) {
  const void *entry = *((void **)slot);
  return entry == HTAB_EMPTY || entry == HTAB_DELETED;
}

INLINE hashval_t
htab_iterative_hash(const void *k_in,
                    size_t length,
                    hashval_t initval) {
  const unsigned char *k = (const unsigned char *)k_in;
  hashval_t a, b, c, len;

  len = (hashval_t)length;
  a = b = 0x9e3779b9;
  c = initval;
  while (len >= 12) {
    a += (k[0] + ((hashval_t)k[1] << 8) + ((hashval_t)k[2] << 16) + ((hashval_t)k[3] << 24));
    b += (k[4] + ((hashval_t)k[5] << 8) + ((hashval_t)k[6] << 16) + ((hashval_t)k[7] << 24));
    c += (k[8] + ((hashval_t)k[9] << 8) + ((hashval_t)k[10] << 16) + ((hashval_t)k[11] << 24));
    mix(a, b, c);
    k += 12;
    len -= 12;
  }
  if (len) { //simplified method for GNU libiberty's implementation
    unsigned char tail[12];
    memcpy(tail, k, len);
    memset(tail + len, 0, 12 - len);
    k = tail;
    a += (k[0] + ((hashval_t)k[1] << 8) + ((hashval_t)k[2] << 16) + ((hashval_t)k[3] << 24));
    b += (k[4] + ((hashval_t)k[5] << 8) + ((hashval_t)k[6] << 16) + ((hashval_t)k[7] << 24));
    c += ((hashval_t)length + ((hashval_t)k[8] << 8) + ((hashval_t)k[9] << 16) + ((hashval_t)k[10] << 24));
    mix(a, b, c);
  }
  return c;
}

#define HTAB_FOREACH(var, htab, op)                                \
  {                                                                \
    typeof(**htab->slots) **top = htab->slots + htab->cap, **slot; \
    for (slot = htab->slots; slot != top; slot++) {                \
      if (*slot != HTAB_EMPTY && *slot != HTAB_DELETED) {          \
        typeof(**htab->slots) *var = *slot;                        \
        op;                                                        \
      }                                                            \
    }                                                              \
  }

#define FOREACH_HTAB_ENTRY(htab, var)                                                         \
  for (typeof((htab)->slots) slot = (htab)->slots; slot != (htab)->slots + (htab)->cap; slot++) \
    if (*slot != HTAB_EMPTY && *slot != HTAB_DELETED)                                         \
      for (typeof(*slot) var = *slot; var; var = NULL)

#define HTAB_DEFINE_FULL(htab, htype, HASH, EQ, CALLOC, FREE, COPY, DELETE)                \
  struct htab {                                                                            \
    htype **slots;                                                                         \
    unsigned cap, cnt;                                                                     \
    unsigned long nquery, nscan;                                                           \
    const struct prime_ent *prime_cur;                                                     \
  };                                                                                       \
  typedef struct htab htab##_##t;                                                          \
                                                                                           \
  INLINE void htab##_##check_cap(struct htab *htab);                                       \
  INLINE htype **                                                                          \
      htab##_##find_slot_hash(struct htab *htab, const htype *element, hashval_t hash) {   \
    htab##_##check_cap(htab);                                                              \
    htab->nquery++;                                                                        \
                                                                                           \
    hashval_t cap = htab->cap;                                                             \
    htype **avail = NULL;                                                                  \
                                                                                           \
    hashval_t index = hash % htab->prime_cur->prime;                                       \
    htype **slot = htab->slots + index;                                                    \
                                                                                           \
    if (*slot == HTAB_EMPTY)                                                               \
      return slot;                                                                         \
    else if (*slot == (htype*)HTAB_DELETED)                                                        \
      avail = slot;                                                                        \
    else if (EQ(*slot, element))                                                           \
      return slot;                                                                         \
                                                                                           \
    hashval_t hash2 = 1 + hash % (htab->prime_cur->prime - 2);                             \
    while (1) {                                                                            \
      htab->nscan++;                                                                       \
      index += hash2;                                                                      \
      if (index >= cap)                                                                    \
        index -= cap;                                                                      \
      slot = htab->slots + index;                                                          \
      if (*slot == HTAB_EMPTY)                                                             \
        return avail ? avail : slot;                                                       \
      else if (*slot == (htype*)HTAB_DELETED)                                                      \
        avail = avail ? avail : slot;                                                      \
      else if (EQ(*slot, element))                                                         \
        return slot;                                                                       \
    }                                                                                      \
  }                                                                                        \
                                                                                           \
  INLINE htype **                                                                          \
      htab##_##find_slot(struct htab *htab, const htype *element) {                        \
    hashval_t hv = HASH(element);                                                          \
    return htab##_##find_slot_hash(htab, element, hv);                                     \
  }                                                                                        \
  INLINE htype *                                                                           \
      htab##_##find_entry(struct htab *htab, const htype *element, hashval_t hash) {       \
    htab->nquery++;                                                                        \
    hashval_t cap = htab->cap;                                                             \
    htype **avail = NULL;                                                                  \
                                                                                           \
    hashval_t index = hash % htab->prime_cur->prime;                                       \
    htype *entry = htab->slots[index];                                                     \
                                                                                           \
    entry = htab->slots[index];                                                            \
    if (entry == HTAB_EMPTY || entry != (htype*)HTAB_DELETED && EQ(entry, element))                \
      return entry;                                                                        \
                                                                                           \
    hashval_t hash2 = 1 + hash % (htab->prime_cur->prime - 2);                             \
                                                                                           \
    while (1) {                                                                            \
      htab->nscan++;                                                                       \
      index += hash2;                                                                      \
      if (index >= cap)                                                                    \
        index -= cap;                                                                      \
      entry = htab->slots[index];                                                          \
      if (entry == HTAB_EMPTY || entry != (htype*)HTAB_DELETED && EQ(entry, element))              \
        return entry;                                                                      \
    }                                                                                      \
  }                                                                                        \
                                                                                           \
  INLINE void                                                                              \
      htab##_##init(struct htab *htab, hashval_t initial_size) {                           \
    htab->prime_cur = prime_tab;                                                           \
    while (htab->prime_cur->prime * 3 < initial_size * 4)                                  \
      htab->prime_cur++;                                                                   \
                                                                                           \
    htab->nquery = 0;                                                                      \
    htab->nscan = 0;                                                                       \
    htab->cap = htab->prime_cur->prime;                                                    \
    htab->cnt = 0;                                                                         \
    htab->slots = (htype **)CALLOC(htab->cap, sizeof(htype *));                            \
  }                                                                                        \
                                                                                           \
  INLINE void                                                                              \
      htab##_##traverse(struct htab *htab, void (*callback)(htype *, void *), void *arg) { \
    htype **top = htab->slots + htab->cap, **slot;                                         \
    for (slot = htab->slots; slot != top; slot++) {                                        \
      if (*slot != HTAB_EMPTY && *slot != (htype*)HTAB_DELETED) {                                  \
        callback(*slot, arg);                                                              \
      }                                                                                    \
    }                                                                                      \
  }                                                                                        \
                                                                                           \
  INLINE void htab##_##check_cap(struct htab *htab) {                                      \
    if (htab->cap * 3 < htab->cnt * 4) {                                                   \
      htab->prime_cur++;                                                                   \
      htype **old_slots = htab->slots;                                                     \
      htype **top = htab->slots + htab->cap, **slot;                                       \
      htab->cap = htab->prime_cur->prime;                                                  \
      htab->slots = (htype **)CALLOC(htab->cap, sizeof(htype *));                          \
      unsigned long nquery_old = htab->nquery;                                             \
      unsigned long nscan_old = htab->nscan;                                               \
      for (slot = old_slots; slot != top; slot++) {                                        \
        if (*slot != HTAB_EMPTY && *slot != (htype*)HTAB_DELETED) {                                \
          hashval_t hv = HASH(*slot);                                                      \
          htype **new_slot = htab##_##find_slot_hash(htab, *slot, hv);                     \
          *new_slot = *slot;                                                               \
        }                                                                                  \
      }                                                                                    \
      FREE(old_slots);                                                                     \
      htab->nquery = nquery_old;                                                           \
      htab->nscan = nscan_old;                                                             \
    }                                                                                      \
  }                                                                                        \
                                                                                           \
  INLINE void                                                                              \
      htab##_##insert(struct htab *htab, htype **slot, htype *element) {                   \
    if (*slot == HTAB_EMPTY || *slot == (htype*)HTAB_DELETED)                                      \
      htab->cnt++;                                                                         \
    *slot = element;                                                                       \
  }                                                                                        \
                                                                                           \
  INLINE void                                                                              \
      htab##_##delete (struct htab * htab, htype * *slot) {                                \
    DELETE(*slot);                                                                         \
    *slot = (htype*)HTAB_DELETED;                                                                  \
    htab->cnt--;                                                                           \
  }                                                                                        \
                                                                                           \
  INLINE int                                                                               \
      htab##_##pack(struct htab *htab, htype *entries) {                                   \
    int nrec_write = 0;                                                                    \
    htype **top = htab->slots + htab->cap, **slot;                                         \
    for (slot = htab->slots; slot != top; slot++) {                                        \
      if (*slot != HTAB_EMPTY && *slot != (htype*)HTAB_DELETED) {                                  \
        COPY(entries + nrec_write, *slot);                                                 \
        nrec_write++;                                                                      \
      }                                                                                    \
    }                                                                                      \
    return nrec_write;                                                                     \
  }                                                                                        \
                                                                                           \
  INLINE void                                                                              \
      htab##_##destroy(struct htab *htab) {                                                \
    htype **top = htab->slots + htab->cap, **slot;                                         \
    for (slot = htab->slots; slot != top; slot++) {                                        \
      if (*slot != HTAB_EMPTY && *slot != (htype*)HTAB_DELETED) {                                  \
        DELETE(*slot);                                                                     \
      }                                                                                    \
    }                                                                                      \
    FREE(htab->slots);                                                                     \
  }
#define HTAB_COPY_DEFAULT(a, b) memcpy(a, b, sizeof(*(a)))
#define HTAB_DEL_DEFAULT(x)
#define HTAB_DEFINE_CALLOC_FREE(htab, htype, HASH, EQ, CALLOC, FREE) HTAB_DEFINE_FULL(htab, htype, HASH, EQ, CALLOC, FREE, HTAB_COPY_DEFAULT, HTAB_DEL_DEFAULT)
#define HTAB_DEFINE_ESMD(htab, htype, HASH, EQ)           \
  INLINE void *htab##_calloc(size_t nmemb, size_t size) { \
    return esmd_calloc(nmemb, size, #htab "/tab");        \
  }                                                       \
  INLINE void htab##_free(void *ptr) {                    \
    esmd_free(ptr);                                       \
  }                                                       \
  HTAB_DEFINE_CALLOC_FREE(htab, htype, HASH, EQ, htab##_calloc, htab##_free)
#endif
